package org.example.myleet.p516;

/**
 * 官方解
 * 思路：
 * 对于一个回文字符串，头尾各加入一个相同的字符仍然是回文字符串
 * 因此对于i和j(i<j)，如果char(i)==char(j)，则[i,j]内的字符串的最长回文子串长度 = [i+1,j-1]内的字符串的最长回文子串长度 + 2
 * 如果char(i)!=char(j)，则[i,j]内的字符串的最长回文子串长度 = Max([i+1,j]内的字符串的最长回文子串长度, [i,j-1]内的字符串的最长回文子串长度)
 */
public class Solution {
    public int longestPalindromeSubseq(String s) {
        if (s.length() < 2) {
            return 1;
        }
        //代表从i到j最长的回文子串的长度
        int[][] dp = new int[s.length()][s.length()];
        for (int i = 0; i < s.length(); ++i) {
            //初始化状态，对于i==j的状态，回文子串长度都是1
            dp[i][i] = 1;
        }
        //初始化最末尾的两个位置长度的最长回文子串长度
        if (s.charAt(s.length() - 2) == s.charAt(s.length() - 1)) {
            dp[s.length() - 2][s.length() - 1] = 2;
        } else {
            dp[s.length() - 2][s.length() - 1] = 1;
        }
        for (int i = s.length() - 3; i >= 0; --i) {
            //注意i从字符串的结尾开始向头部扫描，因为要从短到长进行动态规划
            for (int j = i + 1; j < s.length(); ++j) {
                //动态规划推导
                if (s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                } else {
                    dp[i][j] = Math.max(dp[i][j - 1], dp[i + 1][j]);
                }
            }
        }
        //结果表示0到s.length() - 1长度内最长回文子串的长度
        return dp[0][s.length() - 1];
    }
}
